Routing vertex disjoint Steiner-trees in a cubic grid and connections to VLSI

Consider a planar grid of size w×n. The vertices of the grid are called terminals and pairwise disjoint sets of terminals are called nets. We aim at routing all nets in a cubic grid (above the original grid holding the terminals) in a vertex-disjoint way. However, to ensure solvability, it is allowed to extend the length and the width of the original grid to w^′=sw and n^′=sn by introducing s-1 pieces of empty rows and columns between every two consecutive rows and columns containing the terminals. Hence the routing is to be realized in a cubic grid of size (s·n)×(s·w)×h. The objective is to minimize the height h. It is easy to show that the required height can be as large as h=Ω(max(n,w)) in the worst case. In this paper we show that if s≥2 then a routing with height can always be found in polynomial time. Furthermore, the constant factor ‘6’ can be improved either by increasing the value of s or by limiting the number of terminals in a net. Possible trade-offs between s and h are discussed and the various constructions presented are compared by measuring the volumes of the routings obtained.     

L形通道布线的展开法

本文提出将L形通道展成直通道的布线方法，对展开后的直通道定义了水平约束、垂直约束、拐角约束、走线约束，利用赋权的混合图反映这四种约束、并逐步将图中的无向边转变成有向边，按照有向图的线网上下关系，完成直通道布线，再收缩冗余布线区变成L形通道布线.     

FLPS-工厂平面布置系统

本文在微机上根据物流系统分析法规定的程式设计了工厂平面布置系统,该系统能按规定打印各阶段所需要的工作表格;采用受控分支搜索的相关平面布置法和人机交互修正法相结合,输出多个优化的布置方案;并用评价体系对各个优化方案进行综合评估.设计结果既能直观地在显示器上显示,又能在绘图仪上绘出.     

An analysis of some linear graph layout heuristics

The worst-case performances of some heuristics for the fixed linear crossing number problem (FLCNP) are analyzed. FLCNP is similar to the 2-page book crossing number problem in which the vertices of a graph are optimally placed on a horizontal “node line” in the plane, each edge is drawn as an arc in one half-plane (page), and the objective is to minimize the number of edge crossings. In FLCNP, the order of the vertices along the node line is predetermined and fixed. FLCNP belongs to the class of NP-hard optimization problems Masuda et al., 1990. In this paper we show that for each of the heuristics described, there exist classes of n-vertex, m-edge graphs which force it to obtain a number of crossings which is a function of n or m when the optimal number is a small constant. This leaves open the problem of finding a heuristic with a constant error bound for the problem.     

基于圆形件排样问题的遗传算法研究

排样性问题是一类优化求解问题,在遗传算法求解过程中,若所用的算法是不收敛的,则无法得到最优解.给出了一种混合式遗传算法,并证明了算法是完全收敛的,能够得到全局最优解.     

基于遗传算法的舰载IMU优化布局

惯性测量单元（IMU）用来为舰载武器系统提供准确的姿态并实时监测舰船甲板的变形，对其数目和位置进行优化具有重要的实用价值．提出了多IMU优化布局的原则，建立了舰载IMU优化布局的数学模型，采用遗传算法对IMU的布局进行了优化求解。仿真结果表明，舰载IMU的布局是影响甲板变形估计精度的一个重要因素，通过对IMU的布局进行优化，减少了舰载武器系统所需IMU的数量；利用优化布局后IMU的输出信息对全舰甲板变形进行估计，估计精度有很大提高。     

The effect of nozzle layout on droplet ejection of a piezo-electrically actuated micro-atomizer

We study here effects of nozzle layout on the droplet ejection of a micro atomizer, which was fabricated with the arrayed nozzles by the MEMS technology and actuated by a piezoelectric disc. A theoretical model was first built for this piezoelectric-liquid-structure coupling system to characterize the acoustic wave propagation in the liquid chamber, which determined the droplet formation out of nozzles. The modal analysis was carried out numerically to predict resonant frequencies and simulate the corresponding pressure wave field. By comparing the amplitude contours of pressure wave on the liquid-solid interface at nozzle inlets with the designed nozzle layout, behaviors of the device under different vibration modes can be predicted. Experimentally, an impedance analyzer was used to measure the resonant frequencies of the system. Three types of atomizers with different nozzle layouts were fabricated for measuring the effect of nozzle distribution on the ejection performance. The visualization experiment of droplet generation was carried out and volume flow rates of these devices were measured. The good agreement between the experiment and the prediction proved that only the increase of nozzles may not enhance the droplet generation and a design of nozzle distribution from a viewpoint of frequency is necessary for a resonant related atomizer. The project supported by the National Natural Science Foundation of China (50405001).     

结构静态拓扑重分析的迭代组合近似方法

提出一种拓扑修改的静态重分析的迭代组合近似方法. 这种方法基本上是两步法. 首先，将新增加的自由度通过Guyan缩减方法凝聚到原始自由度上，形成凝聚方程. 其次， 用迭代组合近似方法求出原始自由度的近似位移，从而求出原结构自由度的位移. 新增加自 由度的位移可以通过恢复得到. 通过板结构的加筋布局优化设计的数值例子表明， 该方法对拓扑修改较大时仍可得到满意的结果.     

Distinctive Features of the Flow past a Flight Vehicle Integrated with an Air-Breathing Engine at High Supersonic Velocities

The aerodynamic characteristics and distinctive features of the flow past hypersonic integral-layout flight vehicles with air-breathing engines intended for cruising atmospheric flight are experimentally investigated. The experiments were conducted on a simplified model designed with regard for the general principles of integration for vehicles of the class considered. The tests were run in a high-speed supersonic wind tunnel over the Mach and Reynolds number ranges 4 M 9 and 10⁵ Re₀ 10⁶.Balance testing was conducted, the pressure distributions over the vehicle surface were measured, the flowfield parameters were determined using a moving total-pressure tube, and flow shadowgraphs were obtained. The measured data are compared with the results of the calculations for three-dimensional inviscid flows. The effects of mounting a nacelle and contouring the internal duct are considered. The effect of the corrections on the duct flow in the absence of jet modeling is estimated.     

Applying Ant System for solving Unequal Area Facility Layout Problems

Ant Colony Optimization (ACO) is a young metaheuristic algorithm which has shown promising results in solving many optimization problems. To date, a formal ACO-based metaheuristic has not been applied for solving Unequal Area Facility Layout Problems (UA-FLPs). This paper proposes an Ant System (AS) (one of the ACO variants) to solve them. As a discrete optimization algorithm, the proposed algorithm uses slicing tree representation to easily represent the problems without too restricting the solution space. It uses several types of local search to improve its search performance. It is then tested using several case problems with different size and setting. Overall, the proposed algorithm shows encouraging results in solving UA-FLPs.